class Solution 
{
private:
    bool BackTrack(vector<int>& list, string S, int length, int index, long long sum, int prev)
    {
        if (index == length)
        {
            return list.size() >= 3;
        }
        long long cur = 0;
        for (size_t i = index; i < length; i++)
        {
            if (i > index && S[index] == '0')
            {
                break;
            }
            cur = cur * 10 + S[i] - '0';
            if (cur > INT_MAX)
            {
                break;
            }

            if (list.size() >= 2)
            {
                if (cur < sum)
                {
                    continue;
                }
                else if (cur > sum)
                {
                    break;
                }
            }
            list.push_back(cur);
            if (BackTrack(list, S, length, i + 1, prev + cur, cur))
            {
                return true;
            }
            list.pop_back();

        }
        return false;
    }
public:
    vector<int> splitIntoFibonacci(string S) 
    {
        vector<int> ret;
        BackTrack(ret, S, S.size(), 0, 0, 0);      // 剪枝+回溯
        return ret;
    }
};